The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
In recent years, use of large-scale networks that exchange, process, and store large amounts of data at high speeds is proliferating. Consequently, demand for reliable data transmission and storage systems is increasing. Referring now to FIG. 1, a typical communication or storage system 10 comprises an information source 12, a source encoder 14, a channel encoder 16, and a modulator 18. The system 10 further comprises a communication channel (or a storage medium) 20. The system 10 further comprises a demodulator 22, a channel decoder 24, a source decoder 26, and a destination 28.
The information source 12 may be an analog source such as a sensor that outputs information as continuous waveforms or a digital source such as a computer that outputs information in a digital form. The source encoder 14 converts the output of the information source 12 into a sequence of binary digits (bits) called an information sequence u. The channel encoder 16 converts the information sequence u into a discrete encoded sequence v called a codeword. The modulator 18 transforms the codeword into a waveform of duration T seconds that is suitable for transmission (or recording).
The waveform output by the modulator 18 is transmitted via the communication channel (or stored in the storage medium) 20. Typical examples of the communication channel 20 are telephone lines, wireless communication channels, optical fiber cables, etc. Typical examples of the storage medium 20 are magnetic disks, tapes, etc. Noise, such as thermal noise, electromagnetic interference, inter-channel crosstalk, etc., may corrupt the waveform.
The demodulator 22 receives the waveform. The demodulator 22 processes each waveform and generates a received sequence r that is either a discrete (quantized) or a continuous output. The channel decoder 24 converts the received sequence r into a binary sequence u′ called an estimated information sequence. The source decoder 26 converts u′ into an estimate of the output of the information source 12 and delivers the estimate to the destination 28. The estimate may be a faithful reproduction of the output of the information source 12 when u′ resembles u despite decoding errors that may be caused by the noise.
System designers strive to find ways to control and minimize errors in data transmission and data storage so that data can be reliably reproduced. For example, system designers strive to design codes and channel encoders (hereinafter encoders) that can combat noise. Implementation of encoders partly depends on types of codes used to encode data.
An encoder using a block code typically divides data into blocks of k bits (symbols) each. A message block is generally represented as a binary k-bit message denoted by u=(u0, u1, . . . , uk-1). The encoder transforms each message u independently into an n-bit codeword denoted by v=(v0, v1, . . . , vn-1), v is also called a code vector of the message u. Thus, a k-bit message block can comprise 2k messages, and the encoder may output 2k codewords for 2k possible messages. A set of 2k codewords of length n is called an (n,k) block code.
When k<n, (n−k) redundant bits may be added to each message to form a codeword. The redundant bits enable a code to combat channel noise. The ability of a code to combat noise can be increased by adding more redundant bits to codewords. For example, more redundant bits can be added by increasing a number of message bits k and a block length n of a code while holding a ratio k/n constant. This, however, may increase complexity and cost of hardware used to implement encoders.
Encoder design may be simplified by using block codes that are linear. This is because linear codes have properties that can be represented mathematically. For example, linear codes may be represented by matrices, polynomials, Tanner graphs, etc. Therefore, encoders using linear codes may be easily implemented using simple hardware such as shift registers.
A block code of length n and 2k codewords is called a linear (n,k) code if a modulo-2 sum of two codewords is also a codeword. In that case, every codeword v in the linear code (n,k) is a linear combination of k linearly independent codewords, g0, g1, . . . , gk-1. That is, v=u0g0+u1g1+ . . . +uk-1gk-1, where ui=0 or 1 for 0≦i<k.
The k linearly independent codewords can be arranged as rows of a k×n matrix as follows.
  G  =            [                                                  g              0                                                                          g              1                                                            ⋮                                                              g                              k                -                1                                                        ]        =          [                                                  g              00                                                          g              01                                            …                                              g                              0                ,                                                                  ⁢                                  n                  -                  1                                                                                                        g              10                                                          g              11                                            …                                              g                              1                ,                                                                  ⁢                                  k                  -                  1                                                                                          ⋮                                ⋮                                                                                          ⋮                                                              g                                                k                  -                  1                                ,                0                                                                        g                                                k                  -                  1                                ,                1                                                          …                                              g                                                k                  -                  1                                ,                                                                  ⁢                                  n                  -                  1                                                                        ]      where gi=(gi0, gi1, . . . , gi,(n-1)) for 0≦i<k.
Thus, if u=(u0, u1, . . . , uk-1) is a message to be encoded, a corresponding codeword is expressed as follows.v=u*G 
                                              ⁢                  =                    ⁢                                    (                                                u                  ⁢                                                                          ⁢                  0                                ,                                  u                  ⁢                                                                          ⁢                  1                                ,                …                ⁢                                                                  ,                                  u                                      k                    -                    1                                                              )                        *                          [                                                                                          g                      0                                                                                                                                  g                      1                                                                                                            ⋮                                                                                                              g                                              k                        -                        1                                                                                                        ]                                                              =                ⁢                              u            ⁢                                                  ⁢            0            ⁢            g            ⁢                                                  ⁢            0                    +                      u            ⁢                                                  ⁢            1            ⁢            g            ⁢                                                  ⁢            1                    +          …          +                                    u                              k                -                1                                      ⁢                          g                              k                -                1                                                        
Rows of matrix G generate the linear code (n,k). Therefore, matrix G is called a generator matrix for the linear code (n,k). Implementing an encoder that uses the linear code (n,k) is simplified because the encoder may store only k rows of the matrix G to form a linear combination of the k rows based on the input message u.
Codewords of linear codes generally comprise a message part and a redundant part. The message part comprises k unaltered information (or message) digits. The redundant part comprises (n−k) parity check digits, which are linear sums of the information digits. A linear (n,k) code may be alternatively specified by a k×n matrix G as follows.
  G  =            [                                                  g              0                                                                          g              1                                                            ⋮                                                              g                              k                -                1                                                        ]        =          [                                                  p              00                                                          p              01                                            …                                              p                              0                ,                                                                  ⁢                                  n                  -                  k                  -                  1                                                                          1                                0                                0                                …                                0                                                              p              10                                                          p              11                                            …                                              p                              1                ,                                                                  ⁢                                  n                  -                  k                  -                  1                                                                          0                                1                                0                                …                                0                                                ⋮                                                                                                                                                    ⋮                                ⋮                                                                                                                                                                                                              ⋮                                                              p                                                k                  -                  1                                ,                0                                                                        p                                                k                  -                  1                                ,                1                                                          …                                              p                                                k                  -                  1                                ,                                                                  ⁢                                  n                  -                  k                  -                  1                                                                          0                                0                                0                                …                                1                              ]      where pij=0 or 1.
If u=(u0, u1, . . . , uk-1) is the message to be encoded, the codeword v is expressed as follows.
                    v        =                ⁢                  (                                    v              ⁢                                                          ⁢              0                        ,                          v              ⁢                                                          ⁢              1                        ,            …            ⁢                                                  ,                          v                              n                -                1                                              )                                        =                ⁢                              (                                          u                ⁢                                                                  ⁢                0                            ,                              u                ⁢                                                                  ⁢                1                            ,              …              ⁢                                                          ,                              u                                  k                  -                  1                                                      )                    *          G                    Thus, vn-k+i=ui for 0≦i<k, and vj=u0p0j+uip1j++uk-1pk-1,j for 0≦j<(n−k). The (n−k) equations for vj are called the parity check equations of the code.
The linear code (n,k) generated by G can also be described as a null space of a (n−k)×n matrix H, where H is called a parity check matrix of the code (n,k) and is expressed as follows.
  H  =      [                            1                          0                          …                          0                                      p            00                                                p            10                                    …                                      p                                          k                -                1                            ,              0                                                            0                          1                          …                          0                                      p            01                                                p            11                                    …                                      p                                          k                -                1                            ,              1                                                            ⋮                                                                                                                          ⋮                          ⋮                                                                                                                          ⋮                                      0                          0                          …                          1                                      p                          0              ,                              n                -                k                -                1                                                                          p                          1              ,                              n                -                k                -                1                                                              …                                      p                                          k                -                1                            ,                              n                -                k                -                1                                                          ]  
Some linear codes are cyclic or quasi-cyclic. An (n,k) linear code is called a cyclic code if every cyclic shift of a codeword is also a codeword. If a codeword v=(v0, v1, . . . , vn-1) is cyclically shifted one place to the right, a resultant codeword is give by v(1)=(vn-1, v0, v1, . . . , vn-2). Thus, if the codeword v is cyclically shifted i places to the right, a resultant codeword is expressed as follows.V(i)=(vn-1, vn-1+1, . . . , vn-1, v0, v1, . . . , vn-1+1)
Cyclically shifting v by i places to the right is equivalent to cyclically shifting v by (n−i) places to the left.
Cyclic codes may be mathematically represented by polynomials. For example, a codeword v=(v0, v1, . . . , vn-1) can be expressed in the form of a polynomial as follows.v(X)=v0+v1X+v2X2+ . . . +vn-1Xn-1 Thus, each codeword corresponds to a polynomial of degree (n−1) or less. For example, if vn-1≠0, the degree of v(X) is (n−1). If vn-1=0, the degree of v(X) is less than (n−1). Since correspondence between v and v(X) is one to one, v(X) is called a code polynomial of v.
Cyclic codes possess full cyclic symmetry. That is, cyclically shifting a codeword of a cyclic code by any number of symbol positions either to the left or to the right results in another codeword. Therefore, encoders using cyclic codes and corresponding decoders can be easily implemented using simple shift registers and logic circuits.
On the other hand, quasi-cyclic codes do not possess full cyclic symmetry. Instead, quasi-cyclic codes possess partial cyclic symmetry. Specifically, a quasi-cyclic code is a linear code wherein cyclically shifting a codeword a fixed number n0≠1 (a multiple of n0) of symbol positions either to the right or to the left yields another codeword. n0, which is an integer, is called a shifting constraint. Thus, a quasi-cyclic code with n0=1 is a cyclic code.
Quasi-cyclic codes can be represented using matrices called circulant matrices or circulants. A circulant is a square matrix (e.g., a k×k matrix). For any given integer m<k, shifting a column (or a row) by m positions results in another column (or row) of the circulant.
A low-density parity check (LDPC) code is defined as a null space of a parity check matrix having row weights and column weights that are small relative to a length of the code and a number of rows in the parity check matrix. Row weights denote number of 1's in rows of the parity check matrix, and column weights denote number of 1's in columns of the parity check matrix. Since row weights and column weights of the parity check matrix are small, the parity check matrix has a low density of 1's. Consequently, the parity check matrix is a sparse matrix and is called a low-density parity check matrix.
If H denotes the low density parity check matrix, λ denotes the column weight of H, and ρ denotes the row weight of H, then the code specified by H is called a low density parity check code or a (λ,ρ)-regular LDPC code. The code is called regular when the column weight λ and the row weight ρ are constant. On the other hand, when all the columns and all the rows of H do not have identical weight, an LDPC code specified by H is called an irregular LDPC code.
Referring now to FIG. 2, Tanner graphs may be used to graphically represent linear codes such as LDPC codes. A Tanner graph G 40 is denoted by G=(V, E), where V is a set of vertices 42 and E is a set of edges 44. V={v1, v2, . . . , v8} and E={a, b, . . . , h}. The Tanner graph G 40 is called a bipartite graph since vertices V 42 can be partitioned into two disjoint subsets V1={v1, v2, v3} and V2={v4, v5, . . . , v8} such that every edge 44 joins a vertex in V1 to a vertex in V2, and no two vertices in V1 or V2 are connected. A number of edges that are incident on a vertex vi is called a degree of the vertex vi and is denoted by d(vi). For example, degree of vertex v2 is three since edges c, d, and e are incident on vertex v2. Vertices may also be called nodes.
Tanner graphs of linear codes display incidence relationships between code bits of the linear codes and parity checksums that check on the code bits. For a linear code of length n specified by a parity check matrix H with J rows, h1, h2, . . . , hJ, a Tanner graph G comprises two sets of vertices V1 and V2. V1 comprises n vertices, v0, v1, . . . , vn-1, that represent n code bits of the code and are called code bit vertices. Code bit vertices are also called symbol nodes or variable nodes. V2 comprises J vertices that represent J parity checksums or equations, s1, s2, . . . , sJ, that the code bits satisfy and are called checksum vertices or check nodes.
A symbol node vi is connected to a check node sj by an edge denoted by (vi, sj) only if the code bit vi is contained in (or checked by) the parity checksum sj. A degree of the symbol node vi is equal to a number of parity checksums that contain vi. Thus, the degree of a symbol node is equal to a number of edges or symbol node edges with which the symbol node connects to its check nodes. Similarly, a degree of the check node sj is equal to a number of code bits that are checked by sj. Thus, the degree of a check node is equal to a number of edges or check node edges with which the check node connects to its symbol nodes.
For a regular LDPC code, degrees of all symbol nodes in a Tanner graph are identical and are equal to a column weight λ of H. Similarly, degrees of all check nodes are identical and are equal to a row weight ρ of H. Such a Tanner graph is said to be regular. This is helpful in generating regular LDPC codes and in implementing encoders that use regular LDPC codes.
On the other hand, an irregular LDPC code is defined by a parity check matrix H having multiple column weights and multiple row weights. Thus, a Tanner graph of the irregular LDPC code comprises symbol nodes having multiple degrees and check nodes having multiple degrees. Consequently, generating irregular LDPC codes and implementing encoders that use irregular LDPC codes is relatively complex.